package Math;
/*
给定一个正整数 n，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？

示例 1:
输入:
8
输出:
3
解释:
8 -> 4 -> 2 -> 1

 */
public class 整数替换 {
/*偶数直接除，如果能尽可能多的运用除法，则下降较快
对于一个数，如果其二进制结尾是01的话，肯定是奇数，-1就可以，
但是如果是11的话，-1以后，只能做一次除法操作，但是+1之后，可以连续做两次除法操作，
因此我们可以对结尾是01还是11来判断实际要进行的操作。
 */
    public int integerReplacement(int n) {
        int res=0;
        while (n!=1) {
			if (n==3) {
				res+=2;
				break;
			}
			if (n == Integer.MAX_VALUE) { //2^31-1
				return 32;
			}
			if ((n&1)==0) { //偶数
				n>>=1;  //n=n/2
			}else {//奇数
				if ((n&2) == 2) {
					n++;
				}else {
					n--;
				}
			}
			res++;
		}
        return res;
    }
}
